package m202405.d27;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/27 13:12
 */
public class Q51 {

    public static void main(String[] args) {
        Q51 q51 = new Q51();
        q51.solveNQueens(1);
    }


    /**
     * 00 01 02 03 04
     * 10 11 12 13 14
     * 20 21 22 23 24
     * 30 31 32 33 34
     * 40 41 42 43 44
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> rs = new ArrayList<>();
        solve(n, 1, new int[n][n], new ArrayList<>(), rs);
        return rs;
    }

    private void solve(int n, int i, int[][] flag, List<int[]> positions, List<List<String>> rs) {
        if (i > n) {
            add2Rs(n, positions, rs);
            return;
        }
        for (int j = 0; j < flag[i - 1].length; j++) {
            if (flag[i - 1][j] == 0) {
                positions.add(new int[]{i - 1, j});
                addFlag(flag, new int[]{i - 1, j}, i);

                solve(n, i + 1, flag, positions, rs);

                positions.remove(positions.size() - 1);
                removeFlag(flag, i);
            }
        }
    }

    private void add2Rs(int n, List<int[]> positions, List<List<String>> rs) {
        List<String> list = new ArrayList<>();
        for (int[] position : positions) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (i != position[1]) {
                    sb.append(".");
                } else {
                    sb.append("Q");
                }
            }
            list.add(sb.toString());
        }
        rs.add(list);
    }

    private void addFlag(int[][] flag, int[] position, int i) {
        //相同行标记
        for (int j = 0; j < flag[position[0]].length; j++) {
            if (flag[position[0]][j] == 0) {
                flag[position[0]][j] = i;
            }
        }
        //相同列标记
        for (int j = 0; j < flag.length; j++) {
            if (flag[j][position[1]] == 0) {
                flag[j][position[1]] = i;
            }
        }
        //方向为‘\’
        int[] start1 = position[1] > position[0] ? new int[]{0, position[1] - position[0]} : new int[]{position[0] - position[1], 0};
        while (start1[0] < flag.length && start1[1] < flag.length) {
            if (flag[start1[0]][start1[1]] == 0) {
                flag[start1[0]][start1[1]] = i;
            }
            start1[0] += 1;
            start1[1] += 1;
        }
        //方向为‘/’
        int[] start2 = position[0] + position[1] >= flag.length ? new int[]{flag.length - 1, position[1] - (flag.length - 1 - position[0])} : new int[]{position[0] + position[1], 0};
        while (start2[0] >= 0 && start2[1] < flag.length) {
            if (flag[start2[0]][start2[1]] == 0) {
                flag[start2[0]][start2[1]] = i;
            }
            start2[0] -= 1;
            start2[1] += 1;
        }
    }

    private void removeFlag(int[][] flag, int i) {
        for (int j = 0; j < flag.length; j++) {
            for (int k = 0; k < flag[j].length; k++) {
                if (flag[j][k] == i) {
                    flag[j][k] = 0;
                }
            }
        }
    }
}
